﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QQ.InterviewQuestions.BinarySearch
{
    internal class BinarySearch
    {
        public int Execute(int[] a ,int searchnum)
        {
            if (a==null || a.Length<=0)
            {
                return -1;
            }

            int middle, left, right;
            left = 0;
            right = a.Length - 1;

            while (left <= right)
            {
                middle = (left + right) / 2;
                if (a[middle] < searchnum)
                {
                    left = middle + 1;
                }
                else if (a[middle] == searchnum)
                {
                    return middle;
                }
                else if (a[middle] > searchnum)
                {
                    right = middle - 1;
                }
                
            }

            return -1;
        }

        public int ExecuteRecursive(int[] a, int searchnum, int left, int right)
        {
            if (a == null || a.Length <= 0)
            {
                return -1;
            }

            int middle;

            if (left <= right)
            {
                middle = (left + right) / 2;

                if (a[middle] < searchnum)
                {
                    return ExecuteRecursive(a, searchnum, middle + 1, right);
                }
                else if (a[middle] == searchnum)
                {
                    return middle;
                }
                else if (a[middle] > searchnum)
                {
                    return ExecuteRecursive(a, searchnum, left, middle - 1);
                }
            }

            return -1;
        }

        public int ExecuteRecursive(int[] a, int searchnum)
        {
            return ExecuteRecursive(a, searchnum, 0, a.Length - 1);
        }


        public int FindClosestNumberIndex(int[] a, int searchnum)
        {
            if (a == null || a.Length <= 0)
            {
                return -1;
            }

            int middle, left, right;
            left = 0;
            right = a.Length - 1;

            while ((left + 1) < right)
            {
                middle = (left + right) / 2;
                if (a[middle] < searchnum)
                {
                    left = middle;
                }
                else if (a[middle] == searchnum)
                {
                    return middle;
                }
                else if (a[middle] > searchnum)
                {
                    right = middle;
                }

            }

            if (Math.Abs(a[left] - searchnum) < Math.Abs(a[right] - searchnum))
            {
                return left;
            }
            else
            {
                return right;
            }
        }
    }
}
